//
// Description: 875. 快速幂
// Created by Loading on 2022/5/25.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 0x01) {
            // LL 防止越界
            res = (LL) res * a % p;
        }
        // LL 防止越界
        a = (LL) a * a % p;
        // 移位
        b >>= 1;
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b, p;
        cin >> a >> b >> p;

        cout << qmi(a, b, p) << endl;
    }

    return 0;
}